package org.shj.suanfa.sort

object InsertSort {
  def main(args: Array[String]): Unit = {
    val arr = List(9,7, 10, 5, 3, 6)
    println(isort(arr))
  }
  
  def isort(xs: List[Int]) : List[Int] = xs match{
    case List() => List()
    case x :: xs1 => insert(x, isort(xs1))
  }
  
  def insert(x: Int, xs: List[Int]) : List[Int] = xs match{
    case List() => List(x)
    case y :: ys => if (x < y) x :: xs
                    else y :: insert(x,ys)
      
  }
}